package J20241102_sort;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description: 排序
 * User: 王圆豪
 * Date: 2024-11-02
 * Time: 21:56
 */
public class Sort {
    /**
     * 类型：直接插入排序
     * 时间复杂度：最好情况：O(N)
     *           最坏情况：O(N^2)
     * 空间复杂度：O(1)
     */
    public static void d_insert_sort(int[] arr){
        select_sort(arr, 1);
    }

    private static void select_sort(int[] arr, int gra){
        for (int i = gra; i < arr.length; i+=gra) {
            int j = i - gra;
            int tmp = arr[i];
            while(j >= 0 && arr[j] > tmp){
                arr[j + gra] = arr[j];
                j-=gra;
            }
            arr[j + gra] = tmp;
        }
    }

    /**
     * 类型：希尔排序
     * 时间复杂度：O(N^1.3)——O(N^1.5)
     * 空间复杂度：O(1)
     * @param arr
     */
    public static void shell_sort(int[] arr){
        for (int i = arr.length/2; i > 0; i/=2) {
            select_sort(arr, i);
        }
    }

    /**
     * 类型：选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * @param arr
     */
    public static void select_sort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]){
                    index = j;
                }
            }
            swap(arr, index, i);
        }
    }

    private static void swap(int[] arr, int index, int i) {
        int tmp = arr[index];
        arr[index] = arr[i];
        arr[i] = tmp;
    }

    /**
     * 类型：堆排序
     * 时间复杂度：O(N*log(N))
     * 空间复杂度：O(1)
     * @param arr
     */
    public static void heap_sort(int[] arr){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int j : arr) {
            heap.add(j);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.poll();
        }
    }

    /**
     * 类型：冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * @param arr
     */
    public static void bubble_sort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]){
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void quick_sort(int[] arr){
        quick(arr, 0, arr.length - 1);
    }

    private static void quick(int[] arr, int l, int r) {
        if (l >= r){
            return;
        }

        int mid = q_sort(arr, l, r);
        quick(arr, l, mid);
        quick(arr, mid + 1, r);
    }

    private static int q_sort(int[] arr, int l, int r) {
        int tmp = arr[l];
        while (l < r){
            while (l < r && arr[r] >= tmp){
                r--;
            }
            arr[l] = arr[r];
            while (l < r && arr[l] <= tmp){
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l] = tmp;
        return l;
    }
}
